package Aleehot100;

import java.util.Arrays;

/**
 * ClassName: c011
 * Package: Aleehot100
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/5/24 11:37
 * @Version 1.0
 * @Since 1.0
 */
public class c011 {
    public static void main(String[] args) {
        //int[] arr = {1,3,-1,-3,5,3,6,7};
        int[] arr = {1, -1};
        //System.out.println(Arrays.toString(maxSlidingWindow(arr, 3)));
        System.out.println(Arrays.toString(maxSlidingWindow(arr, 1)));
    }

    // static int n, MAXLEN = 100001, l = 0 , r = 0;
    // static int[] res ;

    // static int[] queue = new int[MAXLEN];
    // public static int[] maxSlidingWindow(int[] nums, int k) {
    //     l = r = 0;
    //     //Arrays.fill(queue,0);
    //     n = nums.length;
    //     res = new int[n - k + 1];

    //     // 补全 k -1 窗口的队列的信息
    //     for (int i = 0; i < k - 1; i++) {
    //         while(r > l && nums[i] >= nums[queue[r - 1]]) {
    //             r --;
    //         }
    //         queue[r++] = i;
    //     }

    //     for (int i = k - 1; i < n; i++) {
    //         while(r > l && nums[i] >= nums[queue[r - 1]]) {
    //             r --;
    //         }
    //         queue[r++] = i;
    //         res[i - k + 1] = nums[queue[l]];
    //         if(queue[l] == i - k + 1) {
    //             l ++;
    //         }
    //     }
    //     return res;
    // }

    static int MAXLEN = 100000, l = 0, r = 0;
    static int[] queue = new int[MAXLEN];
    static int[] res;

    public static int[] maxSlidingWindow(int[] nums, int k) {
        l = r = 0;
        res = new int[nums.length - k + 1];

        // 初始化队列
        for (int i = 0; i <= k - 1; i++) {
            while(r > l && nums[i] >= nums[queue[r - 1]]) {
                r --;
            }
            queue[r++] = i;
        }

        // 统计结果
        for (int i = k; i < nums.length; i ++) {
            res[i - k] = nums[queue[l]];
            if(i - k == queue[l]) {
                l ++;
            }
            while(r > l && nums[i] >= nums[queue[r - 1]]) {
                r --;
            }
            queue[r ++]= i;
        }
        res[res.length - 1] = nums[queue[l]];
        return res;
    }
}
